package com.lcm.algorithm.datatest.dp.knapsack.Knapsack01;


import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * @description: 有 N 件物品和一个容量为 C 的背包。第 i 件物品的重量是 w[i]，价值是 v[i]。求解将哪些物品装入背包可使价值总和最大。
 * @author: lcm
 * @create: 2020-04-24 10:09
 **/

public class Knapsack01 {

    public static void main(String[] args){
        System.out.println(get1(10,new int[]{3,4,5},new int[]{4,5,6}));
        System.out.println("------------------");
        System.out.println(get2(10,new int[]{3,4,5},new int[]{4,5,6}));
        System.out.println("------------------");
        System.out.println(get3(10,new int[]{3,4,5},new int[]{4,5,6}));
    }

    /**
     * dp[i][c] = max{dp[i-1][c], dp[i-1][c-w[i]]+v[i]}
     * n个物品放入容量为c的背包，找出价值最大的解，
     * 可以讲问题拆分成，i个物品放入容量为j的背包，那么可以分成两种情况：
     * 1.不包含第i个物品，前i-1个物品放入j的背包
     * 2.包含第i个物品，前i-1个物品放入j-c[i]容量的背包+v[i]
     * 注意点：
     * 1.第二种情况，需要j>=c[i]
     * 时间复杂度O(nc) n为物品数量，c为背包容量
     * 空间复杂度O(nc)
     */
    static int get1(int c,int[] w,int[] v){
        int[][] dp=new int[w.length+1][c+1];
        for(int i=1;i<dp.length;i++){
            for(int j=1;j<dp[0].length;j++){
                if(j<w[i-1]){
                    dp[i][j]=dp[i-1][j];
                }else{
                    dp[i][j]=Math.max(dp[i-1][j],dp[i-1][j-w[i-1]]+v[i-1]);
                }
            }
        }
        return dp[w.length][c];
    }

    /**
     * 空间优化:
     * 从二维数组可以看出，下一行其实只和上一行有联系，也就是说只需要存一个一维数组就可以了
     * 时间复杂度O(nc) n为物品数量，c为背包容量
     * 空间复杂度O(c)
     * @return
     */
    static int get2(int c,int[] w,int[] v){
        int[] dp=new int[c+1];
        for(int i=1;i<w.length;i++){
            for(int j=c;j>=w[i];j--){
                dp[j] = Math.max(dp[j], dp[j - w[i]] + v[i]);
            }
        }
        return dp[c];
    }

    static Map<String,Integer> map=new HashMap<>();

    static int get3(int c,int[] w,int[] v){
        return help(w.length-1,c,w,v);
    }

    static int help(int i,int c,int[] w,int[] v){
        String key=i+""+c;
        if(map.containsKey(key)){
            return map.get(key);
        }
        if(c<=0||i<0) return 0;

        int result=help(i-1,c,w,v);
        if(c>w[i]){
            result=Math.max(result,help(i-1,c-w[i],w,v)+v[i]);
        }
        return result;
    }

}
